package com.linyaonan.leetcode.medium._1305;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 给你 root1 和 root2 这两棵二叉搜索树。
 *
 * 请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.
 *
 *
 * 示例 1：
 *
 * 输入：root1 = [2,1,4], root2 = [1,0,3]
 * 输出：[0,1,1,2,3,4]
 *
 * @author: Lin
 * @date: 2020/1/20
 */
public class AllElements {
    List<Integer> first;
    List<Integer> sec;
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        first = new ArrayList<>();
        sec = new ArrayList<>();
        dfsFirst(root1, first);
        dfsFirst(root2, sec);
        List<Integer> result = new ArrayList<>();
        int startFirst = 0;
        int startSec = 0;
        while (true) {
            if (startFirst == first.size()) {
                result.addAll(sec.subList(startSec, sec.size()));
                break;
            }
            if (startSec == sec.size()) {
                result.addAll(first.subList(startFirst, first.size()));
                break;
            }
            if (first.get(startFirst) < sec.get(startSec)) {
                result.add(first.get(startFirst));
                startFirst++;
            } else {
                result.add(sec.get(startSec));
                startSec++;
            }
        }

        return result;
    }

    private void dfsFirst(TreeNode node, List<Integer> list) {
        if (node != null) {
            dfsFirst(node.left, list);
            list.add(node.val);
            dfsFirst(node.right, list);
        }
    }

}
